package com.cat.dataStructure02;

import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/construct-target-array-with-multiple-sums/description/
 * @create 2025/10/21 17:14
 * @since JDK17
 */

public class Solution36 {
    public boolean isPossible(int[] target) {
        PriorityQueue<Long> heap = new PriorityQueue<>((a, b) -> Long.compare(b, a));
        int n = target.length;
        long sum = 0;
        for (long x : target) {
            sum += x;
            heap.add(x);
        }
        while (sum > n) {
            long cur = heap.poll();
            long rest = sum - cur;
            if (rest == 0 || cur - rest < 1) {
                return false;
            }
            long pre = cur % rest == 0 ? rest : cur % rest;
            sum = rest + pre;
            heap.add(pre);
        }

        return true;
    }
}
